package com.jwetherell.my.problems.backtracking;

public class RatInAMaze {

	int [][] maze = new int[][] {
			{1, 0, 0, 0},
	        {1, 1, 0, 1},
	        {0, 1, 0, 0},
	        {1, 1, 1, 1}};
	int mazeWidth = maze[0].length;
	int mazeHeight = maze.length;
	
	public static void main(String[] args) {
		RatInAMaze maze = new RatInAMaze();
		maze.printMaze();
		
		maze.maze[0][0] = 2;
		String resultString = maze.findPath(0,0) ? "Path found" : "Path not found";
		System.out.println(resultString);
		maze.printMaze();
	}

	private boolean findPath(int x, int y) {
		if (x == 3 && y == 3) { // final destination
			maze[3][3] = 2;
			return true;
		}
		
		// move forward
		if (isValidRange(x+1, y)) {
			if (findPath(x+1, y)) {
				maze[x+1][y] = 2;
				return true;
			}
		}
		
		// move downward
		if (isValidRange(x, y+1)) {
			if (findPath(x,y+1)) {
				maze[x][y+1] = 2;
				return true;
			}
		}
		
		return false;
	}

	private boolean isValidRange(int x, int y) {
		if (x>=0 && x<=3 && y>=0 && y<=3 && (maze[x][y] == 1))
			return true;
		return false;
	}

	private void printMaze() {
		for (int i = 0; i < maze.length; i++) {
			for (int j = 0; j < maze[0].length; j++) {
				if (maze[i][j] >= 0 && maze[i][j] <= 9)
					System.out.print(" ");
				System.out.print(maze[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

}